package Algorithm.DoublePointer;

import java.util.Arrays;

public class Leetcode825_适龄的朋友 {
    //一开始用的排序+二分查找，超时了
    class Solution {
        public int numFriendRequests(int[] ages) {
            Arrays.sort(ages);
            int result = 0;

            for(int j = 0; j < ages.length; j++){
                int temp = j;
                while(temp < ages.length-1 && ages[temp] == ages[temp+1] && ages[temp+1]>(int)(ages[temp]*0.5 + 7)){
                    temp++;
                    result++;
                }

                int index = binarySearch(0, j, (int)(0.5*ages[j]) + 7, ages);
                if(index < j){
                    result = result + (j - index);
                }
            }

            return result;
        }

        public int binarySearch(int l, int r, int target, int[] nums){
            int ll = l;
            int rr  = r;

            while(ll <= rr){
                int mid = (ll + rr)/2;
                if(nums[mid] <= target){
                    ll = ll + 1;
                }else{
                    rr = rr - 1;
                }
            }

            return ll;
        }
    }

    //排序+双指针


}
